package com.zjj.lbw.interview.chain;

import com.zjj.lbw.interview.common.ListNode;

/**
 * @author zhanglei.zjj
 * @description 反转链表
 * @date 2023/8/31 15:57
 */
public class LinkedListReverse {
    public static ListNode reverse(ListNode root) {
        ListNode prev = null, next, curr;
        curr = root;

        while (curr != null) {
            // 修改指针前，保存当前节点的下个节点，指针一旦修改就找不到当前节点的下一个节点
            next = curr.next;
            curr.next = prev;
            // 指针前进
            prev = curr;
            curr = next;
        }

        return prev;
    }

    public static ListNode recursion(ListNode root) {
        // 递归终止条件
        if (root.next == null) {
            return root;
        }

        // 递归
        ListNode newHead = recursion(root.next);

        // 公式
        root.next.next = root;
        root.next = null;

        return newHead;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
        //ListNode node = iterate(node1);
        ListNode node_1 = recursion(node1);
        System.out.println(node_1);
    }
}
